# -*- coding: utf-8 -*-
# @File      :算法
# @Author    :liaogan
# @Datetime  :2023/3/8 10:31

"""
二分查找（Binary Search）：二分查找是一种在有序数组中查找特定元素的算法。它的思想是通过将数组分成两半，
然后比较要查找的元素与中间元素的大小，从而缩小查找范围，直到找到目标元素或确定目标元素不存在。

arr：待查找的有序数组
x：要查找的元素
low、high、mid：指针，表示数组中要查找的范围和中间位置
while循环：在查找范围内不断缩小范围，直到找到目标元素或确定目标元素不存在
if、elif、else语句：通过比较中间元素与目标元素的大小，缩小查找范围
return语句：返回查找到的元素的下标，如果没有找到则返回-1
"""

def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    mid = 0

    while low <= high:
        mid = (high + low) // 2
        if arr[mid] < x:
            low = mid + 1
        elif arr[mid] > x:
            high = mid - 1
        else:
            return mid

    return -1

print(binary_search([1, 2, 3, 4, 5, ], 3))


"""
快速排序（Quick Sort）：快速排序是一种基于分治思想的排序算法。它通过选择一个枢轴元素，将数组分成两个子数组，
其中一个子数组的所有元素都小于枢轴元素，另一个子数组的所有元素都大于枢轴元素，然后递归地对子数组进行排序，最终得到一个有序数组。

arr：待排序的数组
if语句：如果数组长度小于等于1，则直接返回数组
else语句：否则选择一个枢轴元素，将数组分成两个子数组
pivot：枢轴元素，可以选择任意一个元素
less、greater：子数组，less数组中的元素都小于等于枢轴元素，greater数组中的元素都大于枢轴元素
列表解析式：使用列表解析式可以很
"""

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        less = [x for x in arr[1:] if x <= pivot]
        greater = [x for x in arr[1:] if x > pivot]
        return quicksort(less) + [pivot] + quicksort(greater)



"""
冒泡排序
这段代码实现了冒泡排序算法，用于对列表中的元素进行排序。第一行定义了一个名为 bubble_sort 的函数，并将列表作为参数传递。
第二行确定了列表的长度，以便在下面的循环中使用。第三行和第四行是两个嵌套的循环，用于比较和交换相邻元素，以确保列表按照升序排序。
最后一行返回排序后的列表


"""

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1] :
                arr[j], arr[j+1] = arr[j+1], arr[j]



"""
选择排序
"""
def selection_sort(array):
    n = len(array)
    # 遍历所有数组元素
    for i in range(n):
        # 找到未排序部分的最小元素
        min_index = i
        for j in range(i + 1, n):
            if array[min_index] > array[j]:
                min_index = j
        # 将找到的最小元素与第一个未排序元素交换
        array[i], array[min_index] = array[min_index], array[i]
    return array


"""
插入排序
"""
def insertion_sort(array):
    n = len(array)
    # 遍历所有数组元素
    for i in range(1, n):
        key = array[i]
        j = i - 1
        # 将比key大的元素向右移动
        while j >= 0 and key < array[j]:
            array[j + 1] = array[j]
            j -= 1
        # 插入key到正确位置
        array[j + 1] = key
    return array



"""
归并排序
"""
def merge_sort(array):
    if len(array) <= 1:
        return array
    else:
        # 分割数组
        mid = len(array) // 2
        left = merge_sort(array[:mid])
        right = merge_sort(array[mid:])
        # 合并两个已排序的数组
        return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    # 比较两个数组元素并合并
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    # 将剩余元素添加到结果数组
    result += left[i:]
    result += right[j:]
    return result

